#pragma once

#define DICT_BOOK_TRESH_MIN 128
#define DICT_BOOK_TRESH_MAX 384

template<class KeyType,class ValType> class CEX DictEntry:public Object
{

public:
	
	virtual const char* __getName(){return "DictEntry";}
	
	// Key and value for this dictionary entry
	KeyType _key;
	ValType _val;

};

template<class KeyType,class ValType> class CEX DictBook:public Object
{

public:
	
	Array<DictEntry<KeyType,ValType>*> _entries;


	virtual const char* __getName(){return "DictBook";}

	~DictBook()
	{
		_entries.clearDelete();
	}

	bool findKey(KeyType key,int& pos) const
	{
		int left = 0;
		int right = _entries.getSize()-1;

		if(right<0)
		{
			pos = 0;
			return false;
		}

		for(;;)
		{
			//printf("left:%i   right:%i\n",left,right);
			if(right==left)
			{
				pos = left;

				if(key==_entries[left]->_key)
					return true;

				if(key>_entries[left]->_key)
					pos++;

				return false;
			}

			int i = left+(right-left)/2;
			DictEntry<KeyType,ValType>* de = _entries[i];

			if(key==de->_key)
			{
				pos = i;
				return true;
			}

			if(key<de->_key)
			{
				right = i-1;
				if(right<left)
					right = left;
			}
			else
			{
				left = i+1;
				if(left>right)
					left = right;
			}
		}
	}

	int checkKey(KeyType key) const
	{
		if(key<_entries[0]->_key)
			return -1;
		if(key>_entries[_entries.getSize()-1]->_key)
			return 1;

		return 0;
	}

};


template<class KeyType,class ValType> class CEX Dict:public Object
{

	Array<DictBook<KeyType,ValType>*> _books;

public:

	
	virtual const char* __getName(){return "Dict";}

	Dict()
	{
	}

	~Dict()
	{
	}

	bool findKey(KeyType key,int& book,int& pos) const
	{
		int left = 0;
		int right = _books.getSize()-1;

		if(right<0)
		{
			pos = 0;
			book = 0;
			return false;
		}

		for(;;)
		{
			if(right==left)
			{
				book = left;
				return _books[book]->findKey(key,pos);
			}

			int i = left+(right-left)/2;
			int x = _books[i]->checkKey(key);

			if(x<0)
			{
				right = i-1;

				if(right<left)
					right = left;
			}
			else if(x>0)
			{
				left = i+1;
				if(left>right)
					left = right;
			}
			else
			{
				left = i;
				right = i;
			}
		}
	}

	void add(KeyType key,ValType val)
	{
		int i,bi;
		DictBook<KeyType,ValType>* book;

		if(findKey(key,bi,i))
			throw Error("Dict::add(): Duplicate key");

		if(_books.getSize()==0)
		{
			book = new DictBook<KeyType,ValType>();
			_books.add(book);
		}
		else
			book = _books[bi];

		DictEntry<KeyType,ValType>* de = new DictEntry<KeyType,ValType>();
		de->_key = key;
		de->_val = val;

		book->_entries.insert(de,i);

		if(book->_entries.getSize()>DICT_BOOK_TRESH_MAX)
		{
			DictBook<KeyType,ValType>* book2 = new DictBook<KeyType,ValType>();
			
			book->_entries.split(book->_entries.getSize()/2,book2->_entries);
			_books.insert(book2,bi+1);
		}
	
	}

	void remove(KeyType key)
	{
		int i,bi;

		if(!findKey(key,bi,i))
			throw Error("Dict::remove(): Key not found");

		DictBook<KeyType,ValType>* book = _books[bi];

		book->_entries.removeDelete(i);

		if(book->_entries.getSize()==0)
		{
			_books.remove(bi);
			delete book;
		}
		else if(book->_entries.getSize()<DICT_BOOK_TRESH_MIN && _books.getSize()>1)
		{

			if(bi)
			{
				_books[bi-1]->_entries.merge(book->_entries);
				book->_entries.clear();
				_books.removeDelete(bi);
			}
			else
			{
				book->_entries.merge(_books[1]->_entries);
				_books[1]->_entries.clear();
				_books.removeDelete(1);
			}

		}

	}

	void clear()
	{
		_books.clearDelete();
	}

	int getSize() const
	{
		return 0;
	}

	ValType operator[](KeyType key) const
	{
		int i,bi;

		if(!findKey(key,bi,i))
			throw Error("Dict::[]: Key not found");

		return _books[bi]->_entries[i]->_val;

		
	}

	bool hasKey(KeyType key) const
	{
		int i,bi;

		return findKey(key,bi,i);
	}

/*
	void test()
	{

		int x = 0;
	
		printf("Checking %i books\n",_books.getSize());

		for(int a=0;a<_books.getSize();a++)
		{
			DictBook<KeyType,ValType>* book = _books[a];
			
			for(int b=0;b<book->_entries.getSize();b++)
			{
				int y = book->_entries[b]->_key;
				if(y<x)
					printf("ASDF\n");
				x=y;
			}

//			delete book;
		}

//		_books.clear();

	}
*/

};





template<class KeyType,class ValType> class CEX SafeDict:public Dict<KeyType,ValType>
{

	Mutex _mtx;

public:

	virtual const char* __getName(){return "SafeDict";}

	SafeDict()
	{
	}

	~SafeDict()
	{
	}

	bool findKey(KeyType key,int& book,int& pos)
	{
		_mtx.lock();

			try
			{
				bool res = Dict<KeyType,ValType>::findKey(key,book,pos);
				_mtx.unlock();

				return res;
			}
			catch(Error)
			{
				_mtx.unlock();
				throw;
			}
	}

	void add(KeyType key,ValType val)
	{
		_mtx.lock();

			try
			{
				Dict<KeyType,ValType>::add(key,val);
			}
			catch(Error)
			{
				_mtx.unlock();
				throw;
			}
			
		_mtx.unlock();
	}

	void remove(KeyType key)
	{
		_mtx.lock();

			try
			{
				Dict<KeyType,ValType>::remove(key);
			}
			catch(Error)
			{
				_mtx.unlock();
				throw;
			}
			
		_mtx.unlock();
	}

	void clear()
	{
		_mtx.lock();

			try
			{
				Dict<KeyType,ValType>::clear();
			}
			catch(Error)
			{
				_mtx.unlock();
				throw;
			}
			
		_mtx.unlock();
	}

	ValType operator[](KeyType key)
	{
		_mtx.lock();

			try
			{
				ValType res = Dict<KeyType,ValType>::operator[](key);
				_mtx.unlock();

				return res;
			}
			catch(Error)
			{
				_mtx.unlock();
				throw;
			}
	}

	bool hasKey(KeyType key)
	{
		_mtx.lock();

			try
			{
				bool res = Dict<KeyType,ValType>::hasKey(key);
				_mtx.unlock();

				return res;
			}
			catch(Error)
			{
				_mtx.unlock();
				throw;
			}
	}
};

